# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 8_heap_sort.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/1/18 14:52
------------------------------------------
    堆排序
    这里需要从小到大排序，所以，要构建最大堆 —— 堆顶是整个堆中最大的元素
"""


def heap_sort(array):
    # 1. 把无序数组构建成最大堆
    # 从子节点索引计算父节点索引的通用公式为 (child_index - 1) // 2
    for i in range((len(array) - 2) // 2, -1, -1):
        down_adjust(i, len(array), array)

    # 2.循环交换集合尾部元素到堆顶，并调节堆产生新的堆顶
    for i in range(len(array) - 1, 0, -1):
        # 最后一个元素和第一个元素进行交换
        temp = array[i]
        array[i] = array[0]
        array[0] = temp

        # 下沉调整最大堆
        # 这里i用作了堆长度，每次堆长度都在减小，因为不断有被删除的暂时最大元素
        down_adjust(0, i, array)


def down_adjust(parent_index, length, array):
    """
        二叉堆节点下沉
        :param parent_index: 待下沉的节点坐标
        :param length: 堆的长度范围
        :param array:  原数组
    """

    # temp，保存父节点的值，用于最后赋值
    temp = array[parent_index]

    # 这里默认用了左孩子的索引计算，为什么没有右孩子的节点计算？别急,这里写哪个都行，后边进行了处理。
    child_index = 2 * parent_index + 1

    while child_index < length:
        # 如果有右孩子，且右孩子的值大于左孩子的值，则定位到右孩子(找出最小的孩子)
        if child_index + 1 < length and array[child_index + 1] > array[child_index]:
            child_index += 1

        # 如果父节点的值大于任何一个孩子的值，则跳出
        if temp >= array[child_index]:
            break

        # 无需正交换，单向赋值即可
        array[parent_index] = array[child_index]
        parent_index = child_index
        child_index = 2 * child_index + 1

    array[parent_index] = temp


def demo():
    my_array = [3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11]
    print(f"排序前：{my_array}")
    heap_sort(my_array)
    print(f"排序后：{my_array}")


if __name__ == '__main__':
    demo()
